// 大O表示法：一种大概的定性的度量算法时间复杂度的函数（随着数据增加算法操作次数的递增加程度）
// 主要的函数更（性能依次变劣的顺序）： O(1)>O(log(n))>O(n)> O(nlog(n)> O(n^2) O(2^n)
// 大O表示法大推断规则：1、如果是常量则抽象成1   2、如果是多项式就保留最高项   3、最高项系数不为1则抽象为1


// 排序算法
function ArratList() {
    this.arr = [];
    this.getArr = function() {
        return this.arr;
    };
    // 交换位置
    this.swap = function(n, m) {
        let temp = this.arr[n];
        this.arr[n] = this.arr[m];
        this.arr[m] = temp;
    }
    ArratList.prototype.insert = function(item) {
        this.arr.push(item);
    };
    ArratList.prototype.string = function() {
        return this.arr.join('-');
    };
}


// 冒泡排序
// 1、冒泡排序代码实现:核心思想是一次比较将最大项目移到最后
// 2、冒泡排序的时间复杂度（比较次数）：(n-1)(n-2)...1 = n(n-1)/2 => n^2  ==> 交换次数 n(n-1)/4 => n^2
ArratList.prototype.bubblesort = function() {
    var length = this.arr.length;
    for(var j = length - 1; j >= 0; j--) {
        for(var i = 0; i < j; i++) {
            if (this.arr[i] > this.arr[i + 1]) {
                this.swap(i, i + 1);
            }
        }
    }
}

// 选择排序
// 1、选择排序代码实现:核心思想是选择出最小项目放在最前
// 2、选择排序的时间复杂度（比较次数）：(n-1)(n-2)...1 = n(n-1)/2 => n^2  ==> 交换次数 （n-1） => n
ArratList.prototype.selectSort = function() {
    var length = this.arr.length;
    for(var j = 0; j < length; j++) {
        var min = j;
        for(var i = j + 1; i < length; i++) {
            if (this.arr[min] > this.arr[i]) {
                min = i;
            }
        };
        this.swap(j, min);
    }
}

// 插入排序:
// 1、插入排序代码实现:核心思想是局部有序
// 2、插入排序的时间复杂度（最多比较次数）n(n-1)/2 => n^2  复制次数最多n(n-1)/2 => n^2  复制的性能消耗较小
ArratList.prototype.insertSort = function() {
    var length = this.arr.length;
    for(var i = 1; i < length; i++) {
        var j = i;
        var temp = this.arr[i];
        while(this.arr[j - 1] > temp && j > 0) {
            this.arr[j] = this.arr[j - 1];
            j--;
        };
       this.arr[j] = temp;
    }
};


// 希尔排序   是对插入排序的优化  (分组增量插入排序)
// 1、希尔排序代码实现:核心思想是通过增量进行分组,分别对每个分组进行插入排序
// 2、希尔排序的时间复杂度高于插入排序
// 3、增量的是 n / 2  n是排序的元素个数

ArratList.prototype.shellSort = function() {
    let length = this.arr.length;
    // 获取增量
    let gap = Math.floor(length / 2);
    while(gap >= 1) {
        for(var i = gap; i < length; i++) {
            let j = i;
            let temp = this.arr[i];
            while(this.arr[j - gap] > temp && j > gap - 1) {
                this.arr[j] = this.arr[j - gap];
                j -= gap;
            };
            this.arr[j] = temp;
        }
        gap = Math.floor(gap / 2);
    }
}



let arrlist = new ArratList();
arrlist.insert(22);
arrlist.insert(11);
arrlist.insert(3);
arrlist.insert(56);
arrlist.insert(87);
arrlist.insert(17);
console.log('原始数据：', arrlist.string());
// arrlist.bubblesort();
// console.log('冒泡排序后数据：', arrlist.string());
// arrlist.selectSort();
// console.log('选择排序后数据：', arrlist.string());
// arrlist.insertSort();
// console.log('插入排序后数据：', arrlist.string());
arrlist.shellSort();
console.log('希尔排序后数据：', arrlist.string());

